package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/n-ary-tree-level-order-traversal/">N 叉树的层序遍历(N-ary Tree Level Order Traversal)</a>
 * <p>给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。</p>
 * <p>树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,3,2,4,null,5,6]
 *                 1
 *              /  |  \
 *             3   2   4
 *            / |
 *           5  6
 *      输出：[[1],[3,2,4],[5,6]]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树的高度不会超过 1000</li>
 *     <li>树的节点总数在 [0, 10^4] 之间</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0429NaryTreeLevelOrderTraversal_M N 叉树的层序遍历(N-ary Tree Level Order Traversal)
 * @see LC0589NaryTreePreorderTraversal_S  N 叉树的前序遍历(N-ary Tree Preorder Traversal)
 * @see LC0590NaryTreePostorderTraversal_S N 叉树的后序遍历(N-ary Tree Postorder Traversal)
 * @since 2025/2/8 11:54
 */
public class LC0429NaryTreeLevelOrderTraversal_M {

    static class Solution {
        public List<List<Integer>> levelOrder(Node root) {
            List<List<Integer>> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                List<Integer> currLevelNodeValList = new ArrayList<>();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    Node currNode = queue.poll();
                    currLevelNodeValList.add(currNode.val);
                    if (currNode.children != null) {
                        for (Node child : currNode.children) {
                            queue.offer(child);
                        }
                    }
                }
                resList.add(currLevelNodeValList);
            }
            return resList;
        }

        private static class Node {
            public int val;
            public List<Node> children;

            public Node() {
            }

            public Node(int _val) {
                val = _val;
            }

            public Node(int _val, List<Node> _children) {
                val = _val;
                children = _children;
            }
        }
    }


}
